import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;

public class LongestTower {

	public static void main(String[] args) {
		LongestTower lt = new LongestTower();
		List<Person> people = new ArrayList<Person>();
		people.add(new Person(65, 100));
		people.add(new Person(70, 150));
		people.add(new Person(56, 90));
		people.add(new Person(75, 190));
		people.add(new Person(60, 95));
		people.add(new Person(68, 110));
		people.add(new Person(65,120));
		people.add(new Person(65, 110));

		System.out.println(lt.getLongestTower(people));
		System.out.println(lt.callNum);
	}

	Hashtable<Person, List<Person>> ht = new Hashtable<Person, List<Person>>();
	int callNum = 0;

	public List<Person> getLongestTower(List<Person> people) {
		callNum++;
		if (people == null || people.size() == 0)
			return null;

		for (Person p : people) {
			if (!ht.containsKey(p)) {
				List<Person> smallP = getSmaller(people, p);

				if (smallP.size() == 0) {
					List<Person> newList = new ArrayList<Person>();
					newList.add(p);
					ht.put(p, newList);
				} else {
					List<Person> longest = getLongestChild(smallP);
					longest.add(p);
					ht.put(p, longest);
				}
			}
		}

		Person lastP = null;
		for (Person p : ht.keySet()) {
			if (lastP == null)
				lastP = p;
			else {
				if (ht.get(p).size() > ht.get(lastP).size())
					lastP = p;
			}
		}

		return ht.get(lastP);
	}

	private List<Person> getLongestChild(List<Person> smallP) {
		List<Person> cPath = new ArrayList<Person>();
		for (Person sp : smallP) {
			List<Person> spList;
			if (ht.containsKey(sp)) {
				spList = ht.get(sp);
			} else {
				spList = getSmaller(smallP, sp);
				spList.add(sp);
				spList = getLongestTower(spList);
			}

			if (spList.size() > cPath.size()) {
				cPath.clear();
				cPath.addAll(spList);
			}
		}
		return cPath;
	}

	private List<Person> getSmaller(List<Person> people, Person p) {
		List<Person> pList = new ArrayList<Person>();
		for (Person per : people) {
			if (per.compareTo(p) < 0)
				pList.add(per);
		}
		return pList;
	}
}

class Person {
	int ht;
	int wt;

	public Person(int _ht, int _wt) {
		this.ht = _ht;
		this.wt = _wt;
	}

	public int compareTo(Person p) {
		if (p.ht == this.ht && p.wt == this.wt)
			return 0;
		else if (this.ht <= p.ht && this.wt <= p.wt)
			return -1;
		else if (this.ht >= p.ht && this.wt >= p.wt)
			return 1;
		else
			return 2;
	}

	@Override
	public String toString() {
		return "[" + ht + "," + wt + "]";
	}

	@Override
	public boolean equals(Object p) {
		if (p == null)
			return false;
		if (!(p instanceof Person))
			return false;

		Person per = (Person) p;
		return this.wt == per.wt && this.ht == per.ht;
	}
}
